#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
#include<iostream>

using namespace std;

int tmp[5010];

int mergesort(vector<int>& nums, int left, int right);

int reversePairs(vector<int>& nums) {
    int n = nums.size();
    int ret = mergesort(nums, 0, n - 1);
    return ret;
}

int mergesort(vector<int>& nums, int left, int right) {
    if (left >= right) return 0;
    int ret = 0;
    int mid = left + ((right - left) >> 1);

    ret += mergesort(nums, left, mid);
    ret += mergesort(nums, mid + 1, right);

    int cur1 = left, cur2 = mid + 1, i = 0;
    while (cur1 <= mid && cur2 <= right) {
        if ((long long)2 * nums[cur2] >= nums[cur1]) cur2++;
        else ret += right - cur2 + 1, cur1++;
    }

    cur1 = left, cur2 = mid + 1, i = 0;
    while (cur1 <= mid && cur2 <= right) {
        if (nums[cur2] >= nums[cur1]) tmp[i++] = nums[cur2++];
        else tmp[i++] = nums[cur1++];
    }
    while (cur1 <= mid) tmp[i++] = nums[cur1++];
    while (cur2 <= right) tmp[i++] = nums[cur2++];

    for (int j = left; j <= right; ++j) nums[j] = tmp[j - left];
    return ret;
}

int main()
{
    vector<int> nums{ 1,3,2,5,6,8 };
    cout << reversePairs(nums);
    return 0;
}
